package cc.wsyw126.java.nowcoder.sword_offer;

import java.util.Stack;

/**
 * Created by Administrator on 2017/4/13.
 */
public class TreeConvertToList {
    private TreeNode head = new TreeNode(0);
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return pRootOfTree;
        inOrder(pRootOfTree);
        TreeNode result = head.right;
        result.left=null;
        return result;
    }

    public void inOrder(TreeNode root) {
        TreeNode mark = head;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp = root;
        while (temp!=null || !stack.isEmpty()) {
            while (temp!=null) {
                stack.push(temp);
                temp= temp.left;
            }
            if (!stack.isEmpty()) {
                TreeNode pop = stack.pop();
                mark.right = pop;
                pop.left=mark;
                mark=pop;
                temp=pop.right;
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        TreeNode root1 = new TreeNode(6);
        TreeNode root2 = new TreeNode(14);
        TreeNode root3 = new TreeNode(4);
        TreeNode root4 = new TreeNode(8);
        TreeNode root5 = new TreeNode(12);
        TreeNode root6 = new TreeNode(16);
        root.left=root1;
        root.right=root2;
        root1.left=root3;
        root1.right=root4;
        root2.left=root5;
        root2.right=root6;
        TreeConvertToList treeConvertToList = new TreeConvertToList();
        TreeNode convert = treeConvertToList.Convert(root);
        while (convert!=null) {
            System.out.print(convert.val + "\t");
            convert=convert.right;
        }

    }
}
